package Sort;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int A[] = {1, 6, 9, 2, 3, 1, 5, 4,123,545,0,45,25,48,2,8,42,8,5};
        insertionSort(A, A.length);
        System.out.println(Arrays.toString(A));
    }

    public static int[] insertionSort(int[] A, int n) {
        int i, j, temp;

        for(i = 1; i < n; i++){
            temp = A[i];
            for(j = i; j > 0 && A[j - 1] > temp; j-- ){
                A[j] = A[j - 1];
            }
            A[j] = temp;
        }

        return A;
    }
}
